import functools
from typing import List


class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)

        if grid[0][0] == -1 or grid[-1][-1] == -1:
            return 0

        @functools.lru_cache(None)
        def dfs(x1, y1, x2):
            y2 = x1 + y1 - x2
            if x1 == n or y1 == n or x2 == n or y2 == n:
                return -200
            if grid[x1][y1] == -1 or grid[x2][y2] == -1:
                return -200
            if x1 == y1 == n - 1:  # x2 == y2 == n - 1
                return grid[n - 1][n - 1]

            if x1 == x2:  # x2 == y2
                ans = grid[x1][y1]
            else:
                ans = grid[x1][y1] + grid[x2][y2]

            ans += max(dfs(x1 + 1, y1, x2 + 1), dfs(x1, y1 + 1, x2 + 1),
                       dfs(x1 + 1, y1, x2), dfs(x1, y1 + 1, x2))

            return ans

        return max(dfs(0, 0, 0), 0)


if __name__ == "__main__":
    # 5
    print(Solution().cherryPickup(grid=[[0, 1, -1],
                                        [1, 0, -1],
                                        [1, 1, 1]]))

    # 测试用例11/59 : 0
    print(Solution().cherryPickup([[1, 1, -1],
                                   [1, -1, 1],
                                   [-1, 1, 1]]))

    # 测试用例18/59 : 15
    print(Solution().cherryPickup([[1, 1, 1, 1, 0, 0, 0],
                                   [0, 0, 0, 1, 0, 0, 0],
                                   [0, 0, 0, 1, 0, 0, 1],
                                   [1, 0, 0, 1, 0, 0, 0],
                                   [0, 0, 0, 1, 0, 0, 0],
                                   [0, 0, 0, 1, 0, 0, 0],
                                   [0, 0, 0, 1, 1, 1, 1]]))
